/**
All functions in this module can be executed at compile time.

Macros:
  DECLREF = $(LINK2 #$1, $(D $1))
  TABLE_SV = <table border="1" cellpadding="4" cellspacing="0">
             <caption>Special Values</caption>
             $0</table>
 */
module nonstd.string;

import std.stdint;
import std.math : abs;


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Returns true if $(D r) starts with $(D s).
 */
bool startsWith(string r, string s) pure nothrow
{
    if (r.length >= s.length)
        return r[0 .. s.length] == s;
    else
        return false;
}

unittest
{
    static assert( startsWith("", ""));
    static assert( startsWith("abc", ""));
    static assert( startsWith("abc", "a"));
    static assert( startsWith("abc", "abc"));
    static assert(!startsWith("ab", "abc"));
    static assert(!startsWith("ab", "c"));
    static assert(!startsWith("", "a"));
}


/***************************************
Returns the leading substring of $(D r) satisfying $(D pred).
 */
string span(alias pred)(string r) pure nothrow
{
    foreach (i, e; r)
    {
        if (!pred(e))
            return r[0 .. i];
    }
    return r;
}

unittest
{
    static bool isDigit(char ch) pure nothrow
    {
        return '0' <= ch && ch <= '9';
    }
    assert(span!(isDigit)("") == "");
    assert(span!(isDigit)("a") == "");
    assert(span!(isDigit)("11") == "11");
    assert(span!(isDigit)("11a") == "11");
}


/***************************************
Returns $(D s) in which all ASCII letters are converted to uppercase.
 */
char toAsciiUpper(char s) pure nothrow
{
    if ('a' <= s && s <= 'z')
        return s - ('a' - 'A');
    else
        return s;
}

unittest
{
    static assert(toAsciiUpper('a') == 'A');
    static assert(toAsciiUpper('1') == '1');
}


/**
Ditto
 */
string toAsciiUpper(string s) pure nothrow
{
    return mapAscii!(toAsciiUpper)(s);
}

unittest
{
    static assert(toAsciiUpper("abCdeF") == "ABCDEF");
}


/*
[internal] Copy-on-write map function for strings.
 */
private string mapAscii(alias map)(string str) pure nothrow
{
    // [workaround]
    static string idup(string s) pure nothrow
    {
        return (s ~ '\0')[0 .. $ - 1];
    }

    string mstr;

    foreach (i, c; str)
    {
        char mc = map(c);

        // copy on write
        if (mc != c && mstr == null)
            mstr = idup(str[0 .. i]);
        if (mstr)
            mstr ~= mc;
    }
    return mstr ? mstr : str;
}


//===================================================================//
// Convertion between number & string
//===================================================================//

// check whether fun(args) throws
version (unittest)
private template throws(alias fun)
{
    bool throws(T...)(T args) nothrow
    {
        try
        {
            // To prevent optimization for pure function call.
            static typeof(fun(args)) invoke(T args)
            {
                return fun(args);
            }
            invoke(args);
            return false;
        }
        catch
        {
            return true;
        }
    }
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/*
[internal] A policy for string-number convertion.
 */
private template RadixPolicy(string charset)
    if (0 < charset.length && charset.length < ubyte.max)
{
    private enum INVALID = ubyte.max;

    // radix.
    enum RADIX = charset.length;

    /**
     * Returns true if $(D c) is a valid digit letter.
     */
    bool isDigit(char c) pure nothrow
    {
        return decodeX(c) != INVALID;
    }

    /**
     * Returns the digit letter that corresponds to $(D n).
     */
    char encode(ubyte n) pure nothrow
    in
    {
        assert(n < RADIX);
    }
    body
    {
        return charset[][n];
    }

    /**
     * Returns the integer that corresponds to the digit $(D c).
     *
     * Throws:
     * $(D Exception) if $(D c) is not a valid digit letter.
     */
    ubyte decode(char c) pure
    {
        const u = decodeX(c);
        if (u == INVALID)
            throw new Exception("invalid digit");
        return u;
    }

    // [internal] Returns INVALID if c is not enumerated in charset.
    private ubyte decodeX(char c) pure nothrow
    {
        foreach (i, valid; charset)
        {
            if (c == valid)
                return cast(ubyte) i;
        }
        return INVALID;
    }
}

// Common radices
private
{
    alias RadixPolicy!("01"              ) Binary;
    alias RadixPolicy!("01234567"        ) Octal;
    alias RadixPolicy!("0123456789"      ) Decimal;
    alias RadixPolicy!("0123456789ABCDEF") Hexadecimal;
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Returns the decimal string representation of the given signed or
unsigned integer $(D num).
 */
string toString(intmax_t num) pure nothrow
{
    if (num < 0)
        return "-" ~ toString(cast(uintmax_t) -num);
    else
        return       toString(cast(uintmax_t)  num);
}

unittest
{
    alias toString to;

    static assert(to(cast(intmax_t) 0) == "0");
    static assert(to(cast(intmax_t) 2147483647) == "2147483647");
    static assert(to(cast(intmax_t) -2147483648) == "-2147483648");
}


/**
Ditto
 */
string toString(uintmax_t num) pure nothrow
{
    if (num == 0)
        return "0";

    string s;
    for (uintmax_t x = num; x != 0; x /= 10)
    {
        const dig = cast(char) ('0' + (x % 10));
        s = dig ~ s;
    }
    return s;
}

unittest
{
    alias toString to;

    static assert(to(cast(uintmax_t) 0u) == "0");
    static assert(to(cast(uintmax_t) 4294967295u) == "4294967295");
}


/***************************************
Returns the hexadecimal string representation of the given floating
point value $(D num).

$(TABLE_SV
  $(TR $(TH $(D num))
       $(TH $(D toHexString(num))))
  $(TR $(TD NaN)
       $(TD $(D_STRING "NaN")))
  $(TR $(TD +&infin;)
       $(TD $(D_STRING "Infinity")))
  $(TR $(TD &minus;&infin;)
       $(TD $(D_STRING "-Infinity")))
)

Example:
--------------------
enum real pi = 3.1415926535897932385;

// toHexString is executable at compile time.
enum string hex = toHexString(pi);
static assert(hex == "0x1.921FB54442D18468p1");

// The returned string is a valid hexadecimal floating point literal.
static assert(mixin(hex) == pi);
--------------------
 */
string toHexString(real num) pure nothrow
{
    // We should handle NaN before anything.
    if (num !<>= 0) return "NaN";

    // Handle negative and special values.
    if (num < 0) return "-" ~ toHexString(-num);
    if (num == 0) return "0x0p0";
    if (num == real.infinity) return "Infinity";

    // x is now positive finite.
    real x = num;
    assert(x > 0);

    /* Extract the exponent of num. The exponent of x will be reduced
     * to zero.
     */
    intmax_t exp = 0;

    while (x <  0x1p-511) { x *= 0x1p+512; exp -= 512; }
    while (x >= 0x1p+512) { x *= 0x1p-512; exp += 512; }

    while (x <  0x1p-31) { x *= 0x1p+32; exp -= 32; }
    while (x >= 0x1p+32) { x *= 0x1p-32; exp += 32; }

    while (x <  0x1p-0) { x *= 0x1p+1; --exp; }
    while (x >= 0x1p+1) { x *= 0x1p-1; ++exp; }

    assert(1 <= x && x < 2);

    /* Convert the mantissa to hex float string.
     */

    // the integer part, which is always 1
    string mant = "1";
    x -= 1;

    // the fraction part
    assert(0 <= x && x < 1);

    if (x != 0)
    {
        mant ~= ".";
        do
        {
            x *= 0x1p4;

            const dig = cast(ubyte) cast(int) x;
            mant ~= Hexadecimal.encode(dig);
            x    -= dig;
        }
        while (x != 0);
    }

    return "0x" ~ mant ~ "p" ~ toString(exp);
}

unittest
{
    // special values
    static assert(toHexString(real.nan) == "NaN");
    static assert(toHexString(+real.infinity) ==  "Infinity");
    static assert(toHexString(-real.infinity) == "-Infinity");
    static assert(toHexString(+0.0) == "0x0p0");
    static assert(toHexString(-0.0) == "0x0p0");

    // positive values
    static assert(toHexString(0x1p0) == "0x1p0");
    static assert(toHexString(0x1p32) == "0x1p32");
    static assert(toHexString(0x1p-32) == "0x1p-32");
    static assert(toHexString(0x1p127) == "0x1p127");
    static assert(toHexString(0x1p-126) == "0x1p-126");
    static assert(toHexString(0x1p512) == "0x1p512");
    static assert(toHexString(0x1p-512) == "0x1p-512");
    static assert(toHexString(0x1p1023) == "0x1p1023");
    static assert(toHexString(0x1p-1022) == "0x1p-1022");

    // a negative value
    static assert(toHexString(-0x1p42) == "-0x1p42");

    // the smallest representable denormal value
    enum dxp = real.min_exp - real.mant_dig;
    enum den = "0x1p" ~ toString(cast(intmax_t) dxp);
    static assert(toHexString(mixin(den ~ "L")) == den);
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Returns the signed (unsigned) integer represented by the given valid
binary, octal, decimal or hexadecimal string $(D str).

Throws:
$(UL
  $(LI $(D Exception) if $(D str) is invalid)
  $(LI $(D Exception) on integer overflow)
)

Example:
--------------------
intmax_t num = toInt("-0xDD");
assert(num == -221);
--------------------
 */
intmax_t toInt(string str) pure
{
    if (str.length == 0)
        throw new Exception("invalid integer");

    if (str[0] == '+')
        return toInt(str[1 ..$]);

    /* We handle a sign and digits separately, and use toUint for
     * parsing the digits. Note that the result of toUint may cause
     * integer overflow when being converted to a signed integer.
     */
    string rem = str;

    const neg = (rem[0] == '-');
    if (neg)
        rem = rem[1 .. $];

    const u = toUint(rem);

    // Check for integer overflow. Notice the axiom: -min = max+1.
    const bound = cast(uintmax_t) intmax_t.max + (neg ? 1 : 0);
    if (u > bound)
        throw new Exception("signed integer overflow");

    const i = cast(intmax_t) u;
    return neg ? -i : i;
}

unittest
{
    static assert(toInt("0") == 0);
    static assert(toInt("42") == 42);
    static assert(toInt("-42") == -42);
    static assert(toInt(toString(intmax_t.max)) == intmax_t.max);
    static assert(toInt(toString(intmax_t.min)) == intmax_t.min);

    // overflow
    static assert(throws!toInt(      toString(uintmax_t.max)));
    static assert(throws!toInt("-" ~ toString(uintmax_t.max)));
}


/**
Ditto
 */
uintmax_t toUint(string str) pure
{
    if (str.length == 0)
        throw new Exception("invalid integer");

    const upstr = toAsciiUpper(str);

    if (startsWith(upstr, "0X"))
        return toUintX!Hexadecimal(upstr[2 .. $]);

    if (startsWith(upstr, "0B"))
        return toUintX!Binary(upstr[2 .. $]);

    if (startsWith(upstr, "0") && upstr.length > 1)
        return toUintX!Octal(upstr[1 .. $]);

    return toUintX!Decimal(upstr);
}

unittest
{
    static assert(toUint("0xABC_DEF") == 0xABCDEF);
    static assert(toUint("0Xfed_cba") == 0xFEDCBA);
    static assert(toUint("0b110_010") == 0b110010);
    static assert(toUint("0B010_011") == 0b010011);
    static assert(toUint("0_777") == 0777);
    static assert(toUint("42") == 42);

    enum max = toString(uintmax_t.max);
    static assert(toUint(max) == mixin(max ~ "UL"));

    // overflow
    static assert(throws!toUint(toString(uintmax_t.max) ~ "0"));

    static if (is(uintmax_t == ulong))
        static assert(throws!toUint("18446744073709551616"));

    // malformed strings
    static assert(throws!toUint("0xG"));
    static assert(throws!toUint("0b2"));
    static assert(throws!toUint("08"));
    static assert(throws!toUint("4.2"));
}


/*
[internal]
 */
private uintmax_t toUintX(alias Base)(string str) pure
in
{
    assert(str.length);
}
body
{
    uintmax_t num = 0;

    foreach (c; str)
    {
        const uc = toAsciiUpper(c);

        if (uc == '_')
            continue; // separator

        const save = num;
        num *= Base.RADIX;
        num += Base.decode(uc);

        if (num < save)
            throw new Exception("integer overflow");
    }
    return num;
}


/***************************************
Returns the floating point value represented by the given valid decimal
or hexadecimal string $(D str). $(D str) can be one of the special
values described in $(DECLREF toHexString).

Throws:
$(UL
  $(LI $(D Exception) if $(D str) is not a valid decimal nor
       hexadecimal string that represents a floating point value)
  $(LI $(D Exception) on exponent overflow)
)

Example:
--------------------
real num = toReal("0x3.243F6A8885A308Dp0");
assert(num == 3.1415926535897932385);
--------------------
 */
real toReal(string str) pure
{
    if (str.length == 0)
        throw new Exception("invalid floating point literal");

    // for case-insensitive comparison
    const upstr = toAsciiUpper(str);

    if (upstr == "NAN")
        return real.nan;

    if (str[0] == '-')
        return -toReal(str[1 .. $]);

    if (upstr == "INFINITY")
        return real.infinity;

    if (startsWith(upstr, "0X"))
        return toRealX!Hexadecimal(upstr[2 .. $], 'P', 2);

    return toRealX!Decimal(upstr, 'E', 10);
}

unittest
{
    static bool eq(real a, real b) pure nothrow
    {
        const r = a - b;
        return (r < 0 ? -r : r) < (real.epsilon * 10);
    }

    // Special values
    enum n0 = toReal("0");
    static assert(n0 == 0);

    enum nan = toReal("NaN");
    static assert(nan !<>= 0);

    enum pinf = toReal("Infinity");
    static assert(pinf == real.infinity);

    enum ninf = toReal("-Infinity");
    static assert(ninf == -real.infinity);

    // decimal floats can be inexact
    enum n1 = toReal("42");
    static assert(eq(n1, 42));

    enum n2 = toReal("-.31830988618379067154");
    static assert(eq(n2, -.31830988618379067154));

    enum n3 = toReal("3.1415926535897932385");
    static assert(eq(n3, 3.1415926535897932385));

    // with decimal exponent
    enum n4 = toReal("42e42");
    static assert(eq(n4, 42e42));

    enum n5 = toReal("-.0031830988618379067154E2");
    static assert(eq(n5, -.0031830988618379067154E2));

    enum n6 = toReal("314.15926535897932385e-2");
    static assert(eq(n6, 314.15926535897932385e-2));

    // hexadecimal floats must be exact
    enum n7 = toReal("0xDDp2");
    static assert(n7 == 0xDDp2);

    enum n8 = toReal("-0x.aaaaP-2");
    static assert(n8 == -0x.aaaaP-2);

    enum n9 = toReal("0x1.921FB54442D18468p1");
    static assert(n9 == 0x1.921FB54442D18468p1);

    // denormal
    enum dxp = real.min_exp - real.mant_dig;
    enum den = "0x1p" ~ toString(cast(intmax_t) dxp);
    static assert(0 < toReal(den) && toReal(den) < real.min);

    // overflow
    enum of = "0x1p" ~ toString(cast(intmax_t) real.max_exp + 1);
    static assert(throws!toReal(      of));
    static assert(throws!toReal("-" ~ of));
}


/*
[internal]
 */
private real toRealX(alias Base)(
        string str, char expchar, real expbase) pure
out(r)
{
    assert(r <>= 0);
    assert(abs(r) <= real.max);
}
body
{
    string rem = str;
    real   num = 0;

    /* We first build a mantissa as a pure decimal fraction, regardless
     * of the actual position of the decimal point; and we will fix the
     * position of the decimal point later.
     */
    real weight = 1; // place weight for each figure
    uint intfigs;    // number of figures in the integer part
    bool infrac;     // true in the fraction part

    while (rem.length && rem[0] != expchar)
    {
        // embedded separator
        if (rem[0] == '_')
        {
            rem = rem[1 .. $];
            continue;
        }

        // count the number of figures in the integer part
        if (!infrac)
        {
            if (rem[0] == '.')
            {
                infrac = true;
                rem = rem[1 .. $];
                continue;
            }
            ++intfigs;
        }

        // read in a figure
        const fig = rem[0];
        rem = rem[1 .. $];

        weight *= 1.L / Base.RADIX;
        num    += Base.decode(fig) * weight;
    }

    if (intfigs == 0 && !infrac)
        throw new Exception("at least one figure is required");

    // Fix the position of the decimal point.
    num *= pow(cast(real) Base.RADIX, intfigs);

    /* Parse the remaining string as the exponent. It is a decimal
     * string, so we use the toInt for parsing it. Beware of overflow!
     */
    if (rem.length)
    {
        if (rem[0] != expchar)
            throw new Exception("exponent is expected");
        rem  = rem[1 .. $];
        num *= pow(expbase, toInt(rem));
    }

    if (abs(num) > real.max)
        throw new Exception("floating point overflow");

    return num;
}


/*
[workaround] cannot evaluate std.math.pow at compile time
 */
private real pow(real num, intmax_t exp) pure nothrow
{
    if (exp < 0)
        // use 1/num (rather than 1/pow) to allow denormal result
        return pow(1 / num, -exp);

    real mult = num;
    real p    = 1;
    for (intmax_t r = exp; r != 0; r >>= 1)
    {
        if (r & 1)
            p *= mult;
        mult *= mult;
    }
    return p;
}

// ditto
private real pow(real num, uint exp) pure nothrow
{
    return pow(num, cast(intmax_t) exp);
}

unittest
{
    static assert(pow(0x1p+1L, cast(intmax_t) +42) == 0x1p+42);
    static assert(pow(0x1p+1L, cast(intmax_t) -42) == 0x1p-42);
    static assert(pow(0x1p-1L, cast(intmax_t) +42) == 0x1p-42);
    static assert(pow(0x1p-1L, cast(intmax_t) -42) == 0x1p+42);

    // denormal
    static assert(pow(0x1p1L,
            cast(intmax_t) (real.min_exp - real.mant_dig)) > 0);
}


